package shuanfa.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr=new int[]{3,4,6,7,2,7,2,8,0};
        int[] array = new int[80000];
        for (int i = 0; i < 80000; i++) {
            array[i]=(int)(Math.random()*80000);
        }
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String format = simpleDateFormat.format(new Date());
        System.out.println("排序前时间：" + format);
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
        String format1 = simpleDateFormat.format(new Date());
        System.out.println("排序后的时间：" + format1);
    }

    private static void quickSort(int[] arr,int left,int right) {
        if (left<right){
            int start = arr[left];//定义第一个元素为初始基准值
            int high = right;//初始高位
            int low = left;//初始低位
            while (low<high){
                //如果高位数大于基准数，高位下标左移一位 直至找到比基准值小的那个数
                while (low<high && arr[high] >= start){
                    high--;
                }
                arr[low] = arr [high];
                //如果低位数小于于基准数，低位下标右移一位 直至找到比基准值大的那个数
                while (low<high && arr[low] <= start){
                    low++;
                }
                arr[high] = arr [low];
            }
            arr[low] = start;//中间值为基准值
            quickSort(arr,left,low -1);
            quickSort(arr,low +1 ,right);
        }
    }
}
